COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00017 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a14.tex[154,phy] \today\hfill}
\line{\copyright July 2, 1984 Robert W. Floyd\hfill}


\def\es{\emptyset}
\bigskip
The natural numbers are defined by:

\smallskip
\display 40pt:(1):
The empty set $\emptyset$ is a natural number, known as 0.

\smallskip
\display 40pt:(2):
If $n$ is a natural number, the set $n∪\{n\}$ is a natural number, known
as $S(n)$, the {\sl successor\/} of~$n$.
$$\eqalign{S(0)&=\emptyset ∪\{\emptyset\}=\{0\}=1\,.\cr
S(1)&=\{0\}∪\{1\}=\{0,1\}=2\,.\cr
S(2)&=\{0,1\}∪\{2\}=\{0,1,2\}=3\,, \hbox{ etc.}\cr}$$

\display 40pt:(3):
Nothing else is a natural number.

\smallskip\noindent
The common names for the natural numbers are a useful shorthand; without
them, the successive natural numbers would be:
$$\vcenter{\halign{$\lft{#}$\cr
\emptyset\cr
\{\emptyset\}\cr
\bigl\{\emptyset,\{\emptyset\}\bigr\}\cr
\bigl\{\es,\{\es\},\{\es,\{\es\}\}\bigr\}\cr
\bigl\{\es,\{\es\},\{\es,\{\es\}\},\{\es,\{\es\},\{\es,\{\es\}\}\}\bigr\}\cr}}$$
If $S$ is any finite set, the cardinality of $S$, $|S|$, is the unique
natural number which has a 1--1 correspondence with~$S$. If $S$ is a natural
number, $|S|=S$. Define $\omega$ as the set of all natural numbers.
If $n$ is a natural number and $S$ is a set, the sequences of length~$n$
over $S$ are the functions from $n$ to~$S$. In general the finite
sequences are sequences of length $n$ over $S$ for some $n\in\omega$.
An infinite sequence over $S$ is a function from $\omega$ to~$S$.

If $f$ and $g$ are two finite sequences over $S$, then the concatenation
$f\otimes g$ is defined as the sequence $h$ of length $|f|+|g|$ such that
$$\vcenter{\halign{$\lft{#}$\cr
0≤x<|f|⊃h(x)=f(x)\cr
|f|≤x<|f|+|g|⊃h(x)=g\bigl(x|f(x)|\bigr)\,.\cr}}$$
Finite sequences are named by writing their values on successive natural numbers,
separated by commas and enclosed in angle brackets $\langle\,\rangle$.
Thus the sequence which is the function
$$\vbox{\tabskip=0pt\offinterlineskip
\halign{\ctr{#}\quad&\vrule#&\strut\quad\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad
&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad
&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\cr
&\omit&0&1&2&3&4&5&6&7&8&$\cdots$\cr
&\multispan{11}\hrulefill\cr
&height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit\cr
0&&&&X\cr
1&&&&&X\cr
2&&&&&&&X\cr
3&&&&&&&&&X\cr
&height2pt\cr
&\multispan{11}\hrulefill\cr}}$$
is written $\langle 2,3,5,7\rangle$.

If $S$ is a finite set of characters, the {\sl strings\/} over~$S$ are
the sequences over~$S$. Often the choice of~$S$ is given by context,
and we speak simply of strings. Concatenation is defined on strings as on
sequences in general. The string $\langle a,b,c,a\rangle$ is ordinarily
abbreviated $abca$ if no ambiguity can result. The unique string of length~0
is the empty sequence $\langle\,\rangle$, and is known as~$\Lambda$,
the {\sl empty string}. Because the abbreviated form of the empty string
is invisible, it is not ordinarily used in writing.

For sequences in general, and strings in particular,
$$(x\otimes y)\otimes z=x\otimes (y\otimes z)\,,$$
so the results of several concatenations are usualy written unparenthesized
as $x\otimes y\otimes z\otimes\,\cdots$
$$x\otimes\Lambda=\Lambda\otimes x=x\,.$$

Another word for a sequence of length $n$ over $S$ is an $n$-tuple over~$S$.
The 2-tuples are also known as {\sl ordered pairs}, the 3-tuples as
{\sl ordered triples}, etc.

If $f$ is a sequence, the $i$th element of the sequence is $f(i)$, often
written [RWF: FIX]
$fi$. If $f=f↓1\otimes f↓2\otimes f↓3$, we say $f↓2$ is a substring
of~$f$. The substring relation is reflexive and transitive; $f$~and $\Lambda$
are always substrings of~$f$. For many purposes, the strings of length~1
are identified with their values at~0. In particular, the abbreviated
form of writing strings does not distinguish $\langle a\rangle$ from~$a$.
When in doubt, assume that $a$ means~$\langle a\rangle$, and that $abc$
means $\langle a\rangle\otimes\langle b\rangle\otimes\langle c\rangle
=\langle a,b,c\rangle$.

The subsequences of a sequence $x$ are defined thus:

\smallskip
\display 40pt:(1):
The only susequence of $\langle\,\rangle$ is $\langle\,\rangle$.

\smallskip
\display 40pt:(2):
The subsequences of $\langle a\rangle$ are $\langle\,\rangle$ and
$\langle a\rangle$.

\smallskip
\display 40pt:(3):
The subsequencesof $x\otimes y$ are the sequences $x↓1\otimes y↓1$ where
$x↓1$ is a subsequence of~$x$, $y↓1$~a subsequence of~$y$.

\smallskip\noindent
Notice that $abc$ has $ac$ as a subsequence but not as a substring.
A~sequence of length~$n$ has (at most) ???? substrings, $n+1$~prefixes,
$n+1$~suffixes, and $2↑n$~subsequences.

\smallskip
{\bf Exercise:} What are the subsequences, etc., of $abcbac$?

\smallskip
A language $L$ over $\Sigma$ is a (finite or infinite) set of strings
over~$\Sigma$. We use $L↓1\otimes L↓2$ to mean
$\{\,x↓1\otimes x↓2\mid x↓1\in L↓1,x↓2\in L↓2\,\}$. When
no ambiguity results, we write $L↓1L↓2$.

Languages can be raised to powers:
$$\eqalign{L↑0&=\{\Lambda\}\,,\cr
L↑{i+1}&=L↑i\otimes L\cr}$$
so $L↑1=L$, $L↑2=L\otimes L$, etc.

\smallskip
{\bf Exercise:} Show that $\otimes$ on languages is an associative
operation with $\epsilon =\{\Lambda\}$ as identity.

\smallskip
The concatenative closure $L↑{\ast}$ of a language $L$ is the smallest
set of strings which includes $\Lambda$ and $L$ and is closed under
concatenation; $L↑{\ast}=\bigcup↓{i≥0}L↑i$. Define $L↑+=\bigcup↓{i≥1}L↑i$.
Basic identities are:
$$\eqalign{L↑{\ast}&=\{\Lambda\}∪LL↑{\ast}\cr
LL↑{\ast}&=L↑{\ast}L=L↑+\cr
L↑iL↑j&=L↑{i+j}\,.\cr}$$
If $x$ is a string, the language $\{x\}$ is written $x$ where no
ambiguity results.

If $x$ and $y$ are strings, the {\sl shuffles\/} of $x$ and~$y$ are all
strings $x↓1\otimes y↓1\otimes x↓2\otimes y↓2\otimes\,\cdots\,\otimes
x↓n\otimes y↓n$ where $x↓1\otimes x↓2\otimes\,\cdots\,\otimes x↓n=x$
and
$y↓1\otimes y↓2\otimes\,\cdots\,\otimes y↓n=y$; the shuffle of languages
$L↓1$ and $L↓2$ is $∪$~shuffle $(x,y)\mid x\in L↓1,y\in L↓2$.

The regular language $R↓0$ over alphabet $\Sigma$ are a class of languages
defined:

\smallskip
\display 40pt:(1):
$\emptyset \in R↓0$

\smallskip
\display 40pt:(2):
If $a\in\Sigma$, $\{\langle a\rangle\}\in R↓0$

\smallskip
\display 40pt:(3):
$\{\Lambda\}\in R↓0$

\smallskip
\display 40pt:(4):
If $L\in R↓0$, $L↑{\ast}\in R↓0$

\smallskip
\display 40pt:(5):
If $L↓1,L↓2\in R↓0$, $L↓1\otimes L↓2$ and $L↓1∪L↓2\in R↓0$

\smallskip
\display 40pt:(6):
If $L↓1,L↓2\in R↓0$, $L↓1\cap L↓2$ and ${\bar L}↓1=\Sigma↓1↑{\ast}-L↓1\in R↓0$.

\smallskip
By these definitions, if $\Sigma =\{a,b\}$, some regular languages over~$\Sigma$
are:
$$\vcenter{\halign{$\rt{#}\;$&$\lft{#}$\qquad&$\rt{#}\;$&$\lft{#}$\cr
L↓1&=\emptyset&L↓{12}&=bb\cr
L↓2&=a&L↓{13}&=ba↑{\ast}\cr
L↓3&=b&L↓{14}&=b↑+\cr
L↓4&=\Lambda&L↓{15}&=a↑{\ast}b\cr
L↓5&=a↑{\ast}&L↓{16}&=a↑{\ast}b↑{\ast}\cr
L↓6&=b↑{\ast}&L↓{17}&=b↑{\ast}a\cr
L↓7&=L↓2\otimes L↓2=aa&L↓{18}&=b↑{\ast}a↑{\ast}\cr
L↓8&=ab&L↓{19}&=\{a,b\}\cr
L↓9&=a\otimes a↑{\ast}=a↑+&L↓{20}&=a\cup b↑{\ast}\cr
L↓{10}&=ab↑{\ast}&L↓{21}&=b\cup a↑{\ast}\cr
L↓{11}&=ba&L↓{22}&=a↑{\ast}\cup b↑{\ast}\cr}}$$
The above are highly abbreviated;
$$L↓{16}=\{\langle a\rangle\}↑{\ast}\otimes\{\langle b\rangle\}↑{\ast}$$

Given a set of regular equations,
$$\eqalign{A↓1&=f↓1(A↓1,A↓2,\ldots,A↓n)\cr
\vdots\cr
A↓n&=f↓n(A↓1,A↓2,\ldots,A↓n)\cr}$$
when can they have more than one solution? Assume $f↓i$ is a union of
concatenations of variables and strings.

We determine for each variable whether it can be $\Sigma↓{\ast}$, and whether
it can include~$\Lambda$. Initially assume both true for each variable,
and cross off variables from the lists by these rules:
$$A=g↓1\cup g↓2\cup \ldots \cup g↓k$$
remains a $\Sigma↑{\ast}$ variable only if there is a $g↓i$ in which all
variables are $\epsilon$-variables, there are no terminals, and there is
at least one $\Sigma↑{\ast}$ variable.

$A$ remains an $\epsilon$-variable if some $g↓i$ consists entirely
of $\epsilon$-variables (possibly $g↓i=\epsilon$). (By induction,
a~$\Sigma$-variable is an $\epsilon$-variable.)

\medskip
\noindent
Regular Algebra:

Besides the usual laws of set theory for $\emptyset$, $\cap$, $\cup$,
$\sim$ (e.g., $\emptyset\cap x=\emptyset$), there are laws for
concatenation and $\ast$:
$$\vcenter{\halign{$\rt{#}\;$&$\lft{#}$\qquad&\lft{#}\cr
(X\otimes Y)\otimes Z&=X\otimes (Y\otimes Z)&associativity\cr
X\otimes\epsilon&=\epsilon\otimes X=X&identity\cr
(X\cup Y)\otimes Z&=X\otimes Z\cup Y\otimes Z&distributivity\cr
(X\cap Y)\otimes Z&\subseteq X\otimes Z\cap Y\otimes Z\cr
X\otimes \emptyset&=\emptyset\otimes X=\emptyset\cr
(X↑{\ast})↑{\ast}&=x&idempotency\cr
X↑{\ast}&=\epsilon\cup XX↑{\ast}\cr
X\otimes X↑{\ast}&=X↑{\ast}\otimes X\cr
\emptyset↑{\ast}&=\epsilon↑{\ast}=\epsilon\cr
X↑{\ast}\otimes X↑{\ast}&=X↑{\ast}\cr
X↑{\ast}\cup X&=X↑{\ast}\cr
X↑{\ast}\cup\epsilon&=X↑{\ast}\cr}}$$

\vfill\eject\end